package leetcode.双指针法;

/**
 * 接雨水
 *
 * 考察双指针
 *
 * 整个水容量的计算是一块一块累加起来的
 */
public class Test42接雨水 {

    // 双指针法
    public static int trap(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        // 左右两个指针，一头一尾开始遍历，首先找到自己这一边的局部最高点，只要比最高点小就可以装水。
        int leftPoint = 0, rightPoint = height.length - 1;
        int area = 0;
        // 用来保存左右两边最高的柱子
        int leftElementMax = 0, rightElementMax = 0;
        while (leftPoint <= rightPoint) {
            // 确定自己这一边的局部最高点
            leftElementMax = Math.max(leftElementMax, height[leftPoint]);
            rightElementMax = Math.max(rightElementMax, height[rightPoint]);
            // 左边比右边矮可以装水，但是要求左边最高的柱子，比他右边相邻的柱子要高
            // 这样才能形成水槽
            /** 左       右
             *          ||
             *  ||  中  ||
             *  ||  ||  ||
             */
            /** 左                       右
             *                           ||
             *  ||  中         ||        ||
             *  ||  ||         ||        ||
             */
            if (leftElementMax <= rightElementMax) {
                if (leftElementMax > height[leftPoint]) {
                    // 说明出现下降的情况
                    area += (leftElementMax - height[leftPoint]) * 1;
                }
                leftPoint++;
            } else {
                // 左边比右边高也可以装水，但是右边的要比他左边相邻的要高
                // 这样才能形成水槽
                /** 左                       右
                 *  ||
                 *  ||  ||         中        ||
                 *  ||  ||         ||        ||
                 */

                if (rightElementMax > height[rightPoint]) {
                    area += (rightElementMax - height[rightPoint]) * 1;
                }
                rightPoint--;
            }
        }
        return area;
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,2,1,0,1,3,2,1,2,1};
//        int[] nums = {2,0,2};
        System.out.println(trap(nums));
    }
}
